Hacker Rank
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.hr
{
// ----- MO’s Algorithm (Query square root decomposition) ------------------
//
// https://blog.anudeep2011.com/mos-algorithm/
//
// int n - array size
// int[][] qlr - queries [L, R]
// Action<int> addL - add current L
// Action<int> addR - add current R
// Action<int> removeL - remove current L
// Action<int> removeR - remove current R
// Action<int> runQ - run current query
//
// MOs(int n, int[][] qlr, Action<int, int> addL, Action<int, int> removeL,
// Action<int, int> addR, Action<int, int> removeR, Action<int> runQ)
// void Run()
// -------------------------------------------------------------------------
public class MOs
{
int N;
int[][] QLR;
Action<int> AddL, RemoveL, AddR, RemoveR, RunQ;
public MOs(int n, int[][] qlr, Action<int> addL, Action<int> removeL, Action<int> addR, Action<int> removeR, Action<int> runQ)
{
N = n;
QLR = qlr;
AddL = addL;
AddR = addR;
RemoveL = removeL;
RemoveR = removeR;
RunQ = runQ;
}
public void Run()
{
int blockSize = (int)Math.Sqrt(N);
int[] xQ = new int[QLR.Length];
for (int i = 0; i < xQ.Length; i++) xQ[i] = i;
Array.Sort(xQ, (p1, p2) => {
int cmp = (QLR[p1][0] / blockSize).CompareTo(QLR[p2][0] / blockSize);
if (cmp == 0) cmp = QLR[p1][1].CompareTo(QLR[p2][1]);
return cmp;
});
int L = 0;
int R = 0;
for (int i = 0; i < xQ.Length; i++) {
while (L < QLR[xQ[i]][0]) { RemoveL(L); L++; }
while (L > QLR[xQ[i]][0]) { AddL(L); L--; }
while (R < QLR[xQ[i]][1]) { AddR(R); R++; }
while (R > QLR[xQ[i]][1]) { RemoveR(R); R--; }
RunQ(xQ[i]);
}
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using algorithms.graphs;
namespace algorithms.hr
{
// ----- 2-SAT (SAT-isfiability) -------------------------------------------
//
// https://en.wikipedia.org/wiki/2-satisfiability
//
// Depends on:
// -- Graph (algorithms.graphs)
// -- TarjanSCC (algorithms.graphs)
//
// N - number of variables [0..N-1].
//
// int NOT(int a)
// void MUST(int a)
// void OR(int a, int b)
// void XOR(int a, int b)
// void AND(int a, int b)
// void NOT_AND(int a, int b)
//
// bool Possible()
// -------------------------------------------------------------------------
public class SAT2
{
int N = 0;
List<int[]> E = null;
public SAT2(int n)
{
N = n;
E = new List<int[]>();
}
public int c_not(int a)
{
return -a - 1;
}
int c_convert(int a)
{
return a < 0 ? (c_not(a) << 1) ^ 1 : a << 1;
}
void c_must(int a)
{
E.Add(new int[] { a ^ 1, a, 1 });
}
void c_or(int a, int b)
{
E.Add(new int[] { a ^ 1, b, 1 });
E.Add(new int[] { b ^ 1, a, 1 });
}
public void c_xor(int a, int b)
{
c_or(a, b);
c_or(a ^ 1, b ^ 1);
}
void c_and(int a, int b)
{
E.Add(new int[] { a, b, 1 });
E.Add(new int[] { b, a, 1 });
}
void c_not_and(int a, int b)
{
E.Add(new int[] { a, b ^ 1, 1 });
E.Add(new int[] { b, a ^ 1, 1 });
}
public int NOT(int a) { return c_not(a); }
public void MUST(int a) { c_must(c_convert(a)); }
public void OR(int a, int b) { c_or(c_convert(a), c_convert(b)); }
public void XOR(int a, int b) { c_xor(c_convert(a), c_convert(b)); }
public void AND(int a, int b) { c_and(c_convert(a), c_convert(b)); }
public void NOT_AND(int a, int b) { c_not_and(c_convert(a), c_convert(b)); }
public bool Possible()
{
Graph g = new Graph(N * 2, E, true);
TarjanSCC scc = new TarjanSCC(g);
for (int v = 0; v < N; v++)
if (scc.StronglyConnected(v << 1, (v << 1) ^ 1))
return false;
return true;
}
}
// -------------------------------------------------------------------------
}
using System;
namespace algorithms.hr
{
// ----- Segment Tree ------------------------------------------------------
//
// A structure for efficient search of cummulative data.
//
// BASE = 128 * 1024
//
// O(nlogn) preprocessing
// O(logn) a single query
//
// intervals [l, r) [cl, cr)
//
// https://www.hackerrank.com/contests/world-codesprint-9/challenges/box-operations
// https://www.hackerrank.com/contests/world-codesprint-9/challenges/box-operations/editorial
//
// void build(int[] a)
// void put(int l, int r, int delta, int v = 1, int cl = 0, int cr = BASE)
// void divide(int l, int r, int x, int v = 1, int cl = 0, int cr = BASE)
// int getMax(int l, int r, int v = 1, int cl = 0, int cr = BASE)
// int getMin(int l, int r, int v = 1, int cl = 0, int cr = BASE)
// long getSum(int l, int r, int v = 1, int cl = 0, int cr = BASE)
// -------------------------------------------------------------------------
public class SegmentTree
{
const int BASE = 1 << 17;
long[] sum = new long[BASE * 2];
int[] vmin = new int[BASE * 2];
int[] vmax = new int[BASE * 2];
int[] add = new int[BASE * 2];
void update(int u)
{
vmin[u] = Math.Min(vmin[u * 2], vmin[u * 2 + 1]);
vmax[u] = Math.Max(vmax[u * 2], vmax[u * 2 + 1]);
sum[u] = sum[u * 2] + sum[u * 2 + 1];
}
void _put(int u, int val, int len)
{
add[u] += val;
vmin[u] += val;
vmax[u] += val;
sum[u] += val * len;
}
void push(int u, int cl, int cr)
{
if (add[u] != 0)
{
int len = (cr - cl) / 2;
_put(u * 2, add[u], len);
_put(u * 2 + 1, add[u], len);
add[u] = 0;
}
}
public long getSum(int l, int r, int v = 1, int cl = 0, int cr = BASE)
{
if (l <= cl && cr <= r)
return sum[v];
if (r <= cl || cr <= l)
return 0;
int cc = (cl + cr) / 2;
push(v, cl, cr);
return getSum(l, r, v * 2, cl, cc) + getSum(l, r, v * 2 + 1, cc, cr);
}
public int getMax(int l, int r, int v = 1, int cl = 0, int cr = BASE)
{
if (l <= cl && cr <= r)
return vmax[v];
if (r <= cl || cr <= l)
return int.MinValue;
int cc = (cl + cr) / 2;
push(v, cl, cr);
return Math.Max(getMax(l, r, v * 2, cl, cc), getMax(l, r, v * 2 + 1, cc, cr));
}
public int getMin(int l, int r, int v = 1, int cl = 0, int cr = BASE)
{
if (l <= cl && cr <= r)
return vmin[v];
if (r <= cl || cr <= l)
return int.MaxValue;
int cc = (cl + cr) / 2;
push(v, cl, cr);
return Math.Min(getMin(l, r, v * 2, cl, cc), getMin(l, r, v * 2 + 1, cc, cr));
}
public void put(int l, int r, int delta, int v = 1, int cl = 0, int cr = BASE)
{
if (l <= cl && cr <= r)
{
_put(v, delta, cr - cl);
return;
}
if (r <= cl || cr <= l)
return;
int cc = (cl + cr) / 2;
push(v, cl, cr);
put(l, r, delta, v * 2, cl, cc);
put(l, r, delta, v * 2 + 1, cc, cr);
update(v);
}
int func(int p, int q)
{
if (p >= 0) return p / q;
return -((-p + q - 1) / q);
}
public void divide(int l, int r, int x, int v = 1, int cl = 0, int cr = BASE)
{
if (x == 1)
return;
if (l <= cl && cr <= r)
{
int d1 = func(vmin[v], x) - vmin[v];
int d2 = func(vmax[v], x) - vmax[v];
if (d1 == d2)
{
_put(v, d1, cr - cl);
return;
}
}
if (r <= cl || cr <= l)
return;
int cc = (cl + cr) / 2;
push(v, cl, cr);
divide(l, r, x, v * 2, cl, cc);
divide(l, r, x, v * 2 + 1, cc, cr);
update(v);
}
public void build(int[] a)
{
int n = a.Length;
for (int i = 0; i < n; i++)
sum[i + BASE] = vmin[i + BASE] = vmax[i + BASE] = a[i];
for (int i = 0; i < 2 * BASE; ++i)
add[i] = 0;
for (int i = n + BASE; i < 2 * BASE; ++i)
{
sum[i] = 0;
vmin[i] = int.MaxValue;
vmax[i] = int.MinValue;
}
for (int i = BASE - 1; i > 0; --i)
update(i);
}
}
// -------------------------------------------------------------------------
}